let arr = [5, 3, 2, 4, 1]
// 循环取到数组中的每一个元素，当取到某一个元素X时，
// 再次循环取剩下的所有元素依次跟当前这个X进行对比
// 比X小的放X左边，比X大的放X右边

function bubbleSort(arr) {
  // 先保存数组的长度
  const len = arr.length

  for (let i = 0; i < 1; i++) { // O(n)
    for (let j = 0; j < len - 1; j++) { // O(n)
      if (arr[j] > arr[j + 1]) {
        // 交换位置
        // let snap = null
        // snap = arr[i]
        // arr[i] = arr[j]
        // arr[j] = snap

        [ arr[j], arr[j + 1] ] = [ arr[j + 1], arr[j] ]
      }
      console.log(arr);
    }
  }

  return arr
}

// O(n^2)

let newArr = bubbleSort(arr)
console.log(newArr); // [1, 2, 3, 4, 5]



[5, 3, 2, 4, 1]
[3, 5, 2, 4, 1]
[3, 2, 5, 4, 1]
[3, 2, 4, 5, 1]
[3, 2, 4, 1, 5]


[3, 2, 4, 1, 5]
[2, 3, 4, 1, 5]
[2, 3, 4, 1, 5]
[2, 1, 4, 3, 5]
[2, 1, 4, 3, 5]


[2, 1, 4, 3, 5]